package offer;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @Author Elephas
 * @Date 2022/1/24
 **/
public class Jump {
    public static void main(String[] args) {
        final int[] TEST_01 = new int[]{2,3,1,1,4};
        final int[] TEST_02 = new int[]{1,2};
        new Jump().leftToRightJump(TEST_01);
    }

    /*
        解法一：贪心法，从终点向起点迭代，每次寻找最长的一步，时间o(n^2)，空间o(n)
     */

    public int jump(int[] nums){
         return jumpIterator(nums,nums.length - 1,0);
    }
    public int jumpIterator(int[] nums,int current, int iter){
        if(current == 0){
            return iter;
        }else {
            int minOneStep = current;
            for (int i = current; i >= 0; i--) {
                if (nums[i] + i >= current) {
                    minOneStep = i;
                }
            }
            return jumpIterator(nums, minOneStep, iter + 1);
        }
    }
    /*
        贪心法的迭代形式
     */
    public int noneRecJump(int[] nums){
        int current = nums.length - 1;
        int minOneStep = current;
        int iter = 0;
        while (current > 0) {
            for (int i = current; i >= 0; i--) {
                if ((nums[i] + i) >= current) {
                    minOneStep = i;
                }
            }
            current = minOneStep;
            iter++;
        }
        return iter;
    }

    /*
        数组从左到右贪心，o(n)
     */
    public int leftToRightJump(int[] nums){
        int current = 0,iter = 0;
        int maxReach = 0, nextMaxReach, next, target = nums.length - 1;
        while(current < target){
            maxReach = current + nums[current];
            nextMaxReach = maxReach;
            next = current;
            for (int i = current; i <= maxReach; i++) {
                if(i >= target){
                    nextMaxReach = target;
                    next = target;
                    break;
                }else {
                    int canReach = nums[i] + i;
                    if (canReach > nextMaxReach) {
                        nextMaxReach = canReach;
                        next = i;
                    }
                }
            }
            current = next;
            iter++;
        }
        return iter;
    }
    /*
    public int noneRecJump(int[] nums){

        int pre = 0, current = 0, furthest = 0, steps = 0, target = nums.length - 1;
        while(pre < target){
            int range = nums[pre];
            for (current = pre + 1; current <= (pre + range); current++) {
                if(current < target) {
                    int canReach = current + nums[current];
                    if (canReach > furthest) {
                        furthest = canReach;
                    }
                }else{
                    furthest = target;
                    break;
                }
            }
            pre = furthest;
            steps++;
        }
        return steps;
    }

     */
}
